1. Field of the Invention
The present invention relates generally to network search algorithms, and in particular, to a method, apparatus, and article of manufacture for improving the handling of turn restrictions in a network search algorithm.
2. Description of the Related Art
Computer systems are often used to provide directions or paths to a destination. To provide the best/shortest path to a destination, network trace algorithms are commonly used. Network trace algorithms such as a standard Dijkstra algorithm and A* algorithm operate on a model (referred to as a net trace model) in the form of a mathematical graph that is constructed using links (that represent street/road segments) and nodes (that represent intersection and road ends). However, when turn restrictions are introduced, which represent physical and/or legally enforced restrictions (e.g., “no left turn”), the algorithm(s) potentially miss some best paths because the turn restrictions can hide a path that could be followed if the node (intersection) was entered via another link (road). In other words, if a turn restriction is encountered at a node, a node that may be reached but for the turn restriction (referred to as a hidden node) may not be examined. However, such a hidden node may be reached via a different link/road. Accordingly, the best/shortest path may not be found. To address such turn restrictions, a transformed graph approach may be utilized. However, this approach has several disadvantages. These problems may be better understood by describing network search algorithms, turn restrictions, and the transformed graph approach.
Network Search Algorithms
Dijkstra's algorithm was introduced in 1959 and provides a method for solving the shortest-path problem. In a network, it is frequently desired to find the shortest path between two nodes. The weights attached to the edges can be used to represent quantities such as distances, costs, or times. Dijkstra's algorithm is used to find the minimum distance from one given node of a network, called the source node or start node, to all the nodes of the network. In general, the distance along a path is the sum of the weights of that path. The minimum distance from node A to node B is the minimum of the distance of any path from node A to node B. Thus, all paths and their associated distances (also referred to as costs) are determined and the minimum path is then determined.
The A* algorithm is very similar to Dijkstra, but it uses a heuristic function to help prioritize what nodes are searched next. This results in far fewer total nodes being examined before a specific destination node is found. If the heuristic guarantees to always underestimate the actual value, then it can be shown that applying the heuristic continues to find the best route. An example of a heuristic function that satisfies this requirement is the straight-line distance from the examined node to the end point.
Turn Restrictions
Turn restrictions ate part of the net trace model. They are based on network data and are loaded from a database at the same time as the other model information (links and nodes). Each turn restriction identifies a case where it is prohibited to continue a route from one link to another at a specific node. Further, turn restrictions are typically used to represent real life traffic restrictions at specific intersections, where one or more turns are not allowed.
Although turn restrictions may have been supported in the prior art, and all the calculated routes may “obey” them correctly, there is a limitation. The problem with the prior art processing of turn restrictions is that a turn restriction may prevent a full expansion of a node. In other words, not all links leading out of a node may be considered for the best path, depending on which link was used to arrive at the node. Once the node is expanded, however, under the prior art, a re-entry to the same node (via a different link) is prevented, so that some ‘best routes’ may not be found.
Transformed Graph Approach
The transformed graph approach for handling turn restrictions is more fully described in T. Caldwell, On finding Minimum Routes in a Network with Turn Penalties, Communications of the ACM 4(2), 1961, which is incorporated by reference herein. In the transformed graph approach, a road network is transformed into a new network. During this transformation, links in the road network become nodes in the transformed network. Additionally, any two nodes in the transformed network are connected by links if: (1) the corresponding links in the road network are connected at a common node; and/or (2) there is no turn restriction prohibiting traversal from between the corresponding links in the road network.
One advantage of the transformed graph approach is that search algorithms can be used without modification on the transformed network to find minimum cost routes that honor all turn restrictions. However, there are many disadvantages. For example, the original network must be transformed either ahead of time, or at runtime. Further, routes calculated from the transformed network must be translated back into the original network. Additionally, the transformed network is significantly larger than the original network. Accordingly, since runtime performance of the search algorithm is a function of network size, the search algorithms run significantly slower on the transformed network than on the original network.